//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "algobase.h"
#include "allocator.h"
#include "iterator.h"
#include "forward.h"

FC_NAMESPACE_BEGIN


// FC_SLIST_DEBUG
//
// Enabling this allows slist_node<T> to contain templated node
// pointers that point to types of slist_node<T>. This allows
// debuggers to inspect the value of each node and linked nodes
// as well.

#ifdef FC_SLIST_DEBUG
template <class T>
struct slist_node
{
	typedef slist_node<T>	node_type;
	typedef T				value_type;

	node_type* next;
	value_type value;
#else
struct slist_node_base
{
	typedef slist_node_base node_type;
	node_type* next;

	slist_node_base() : next(0) {}
#endif
	void link( node_type* n )
	{
		n->next = next;
		next = n;
	}

	void link_after( node_type* previous )
	{
		next = previous->next;
		previous->next = this;
	}

	void unlink( node_type* previous )
	{
		previous->next = next;
		next = this;
	}

	node_type* get_previous( node_type* root )
	{
		while( root->next != this )
			root = root->next;
		return root;
	}

	void splice_after( node_type* beforeFirst, node_type* beforeLast )
	{
		if( beforeFirst != this && beforeLast != this )
		{
			node_type* first = beforeFirst->next;
			node_type* last = beforeLast->next;

			beforeFirst->next = last;
			beforeLast->next = next;
			next = first;
		}
	}

	void reverse()
	{
		node_type* root = this;
		node_type* first = root->next;
		node_type* p = first->next;
		first->next = root;

		while( p != root )
		{
			node_type* pTemp = p->next;
			p->next = first;
			first = p;
			p = pTemp;
		}

		next = first;
	}

	void swap( node_type* p )
	{
		fc::swap( *this, *p );
		if( next == p ) next = this;
		if( p->next == this ) p->next = p;
	}
};


#ifndef FC_SLIST_DEBUG
template <class T>
struct slist_node : public slist_node_base
{
	typedef slist_node<T>	node_type;
	typedef T				value_type;

	value_type value;
};
#endif

// slist_iterator

template <class T>
class slist_iterator
{
public:
	//iterator_category - std required
	typedef std::forward_iterator_tag	iterator_category;
	typedef forward_iterator_tag		iterator_type;

	typedef T							value_type;
	typedef T*							pointer;
	typedef T&							reference;
	typedef ptrdiff_t					difference_type;
	typedef slist_node<T>				node_type;
	typedef slist_iterator<T>			this_type;

	template <class U, class Allocator> friend class slist;

	slist_iterator() : ptr(0) {}
	slist_iterator( node_type* p ) : ptr(p) {}
	template <class U> slist_iterator( const slist_iterator<U>& i ) : ptr((node_type*)i.base()) {}
	template <class U> slist_iterator( slist_node<U>* p ) : ptr((node_type*)p) {}

	this_type& operator =( node_type* p ) { ptr = p; return *this; }
	template <class U> bool operator ==( const slist_iterator<U>& it ) const { return ptr == it.ptr; }
	template <class U> bool operator !=( const slist_iterator<U>& it ) const { return ptr != it.ptr; }

	reference operator*() const { return ptr->value; }
	pointer operator->() const { return &ptr->value; }

	node_type* base() const { return ptr; }

	this_type& operator ++() { ptr = (node_type*)ptr->next; return *this; }
	this_type  operator ++(int) { this_type temp(*this); ++(*this); return temp; }

protected:
	node_type*	ptr;

};



// slist_base

template <class T, class Allocator>
class slist_base
{
public:
	typedef Allocator								allocator_type;
	typedef slist_node<T>							node_type;
	typedef size_t									size_type;

	slist_base() : m_allocator(), _root(), m_size(0)
		{
			init_head();
		}

	explicit slist_base( const allocator_type& alloc )
		: m_allocator(alloc), _root(), m_size(0)
		{
			init_head();
		}

	allocator_type& get_allocator() { return m_allocator; }
	const allocator_type& get_allocator() const { return m_allocator; }
	void set_allocator( const allocator_type& alloc ) { m_allocator = alloc; }

protected:
	void init_head()
	{
		_root.next = (node_type*)&_root;
	}

	node_type* create_node( const T& value )
	{
		node_type* p = (node_type*)m_allocator.allocate( sizeof(node_type) );
		fc::construct( &p->value, value );
		return p;
	}

	void destroy_node( node_type* p )
	{
		p->~node_type();
		m_allocator.deallocate( p, sizeof(node_type) );
	}

	allocator_type m_allocator;

#ifndef FC_SLIST_DEBUG
	slist_node_base _root;
#else
	node_type _root;
#endif
	size_type m_size;

};



// slist

template <class T, class Allocator>
class slist : public slist_base<T, Allocator>
{
public:
	typedef Allocator								allocator_type;
	typedef slist<T, Allocator>						this_type;
	typedef slist_base<T, Allocator>				base_type;
	typedef slist_node<T>							node_type;
	typedef size_t									size_type;
	typedef T										value_type;
	typedef T*										pointer;
	typedef const T*								const_pointer;
	typedef T&										reference;
	typedef const T&								const_reference;
	typedef slist_iterator<T>						iterator;
	typedef slist_iterator<const T>					const_iterator;
	typedef fc::reverse_iterator<iterator>			reverse_iterator;
	typedef fc::reverse_iterator<const_iterator>	const_reverse_iterator;

	using base_type::create_node;
	using base_type::destroy_node;

	using base_type::m_allocator;
	using base_type::_root;
	using base_type::m_size;

	slist()
		: base_type()
		{
		}

	template <class InputIterator>
	slist( InputIterator first, InputIterator last )
		: base_type()
		{
			insert( begin(), first, last );
		}

	~slist()
		{
			clear();
		}

	iterator		begin()			{ return iterator((node_type*)_root.next); }
	const_iterator	begin() const	{ return const_iterator((node_type*)_root.next); }
	iterator		end()			{ return iterator((node_type*)&_root); }
	const_iterator	end() const		{ return const_iterator((node_type*)&_root); }
	iterator		before_begin()			{ return iterator((node_type*)&_root); }
	const_iterator	before_begin() const	{ return const_iterator((node_type*)&_root); }
	iterator		before_end()			{ return iterator((node_type*)_root.get_previous(&_root)); }
	const_iterator	before_end() const		{ return const_iterator((node_type*)_root.get_previous(&_root)); }
	reverse_iterator		rbegin()		{ return reverse_iterator(end()); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(end()); }
	reverse_iterator		rend()			{ return reverse_iterator(begin()); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(begin()); }
	iterator		previous( iterator pos ) { return iterator( (node_type*)pos.ptr->get_previous(&_root) ); }
	const_iterator	previous( const_iterator pos ) const { return const_iterator( (node_type*)pos.ptr->get_previous(&_root) ); }

	iterator previous( iterator root, iterator pos )
	{
		return iterator( (node_type*)pos.ptr->get_previous(root.ptr) );
	}

	const_iterator previous( const_iterator root, const_iterator pos ) const
	{
		return const_iterator( (node_type*)pos.ptr->get_previous(root.ptr) );
	}

	reference		front()			{ FC_ASSERT(!empty()); return ((node_type*)_root.next)->value; }
	const_reference	front() const	{ FC_ASSERT(!empty()); return ((node_type*)_root.next)->value; }

	bool empty() const		{ return _root.next == &_root; }
	size_t size() const		{ return m_size; }

	void clear()
	{
		erase_after( before_begin(), end() );
	}

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		node_type* prev = (node_type*)&_root;
		node_type* current = (node_type*)_root.next;
		for( ; first != last && current != (node_type*)&_root; ++first )
		{
			prev = current;
			current->value = *first;
			current = (node_type*)current->next;
		}

		if( first != last )
			InsertIterAfter( prev, first, last );
		else
			EraseAfter( prev, (node_type*)&_root );
	}


	void assign( size_t n, const T& value )
	{
		node_type* prev = (node_type*)&_root;
		node_type* current = (node_type*)_root.next;
		for( ; n != 0 && current != (node_type*)&_root; --n )
		{
			prev = current;
			current->value = value;
			current = (node_type*)current->next;
		}

		if( n != 0 )
			InsertValuesAfter( prev, n, value );
		else
			EraseAfter( prev, (node_type*)&_root );
	}

	void push_back( const T& value )
	{
		InsertAfter( (node_type*)((node_type*)&_root)->get_previous(&_root), value );
	}

	void pop_back()
	{
		FC_ASSERT(!empty());
		EraseAfter( (node_type*)((node_type*)&_root)->get_previous(&_root) );
	}

	void push_front( const T& value )
	{
		InsertAfter( (node_type*)&_root, value );
	}

	void pop_front()
	{
		FC_ASSERT(!empty());
		EraseAfter( (node_type*)&_root );
	}

	template <class InputIterator>
	iterator insert( iterator pos, InputIterator first, InputIterator last )
	{
		return insert_after( previous(pos), first, last );
	}

	iterator insert( iterator pos, const T& value )
	{
		return insert_after( previous(pos), value );
	}

	iterator insert( iterator pos, size_t n, const T& value )
	{
		return insert_after( previous(pos), n, value );
	}

	template <class InputIterator>
	iterator insert_after( iterator pos, InputIterator first, InputIterator last )
	{
		return InsertIterAfter( pos.ptr, first, last );
	}

	iterator insert_after( iterator pos, const T& value )
	{
		InsertAfter( pos.ptr, value );
		return iterator( (node_type*)pos.ptr->next );
	}

	iterator insert_after( iterator pos, size_t n, const T& value )
	{
		return InsertValuesAfter( (node_type*)previous(pos).ptr, n, value );
	}

	iterator erase( iterator pos )
	{
		return erase_after( (node_type*)pos.ptr->get_previous(&_root) );
	}

	iterator erase( iterator first, iterator last )
	{
		EraseAfter( (node_type*)first.ptr->get_previous(&_root), (node_type*)last.ptr );
		return last;
	}

	iterator erase_after( iterator pos )
	{
		EraseAfter( pos.ptr );
		return iterator( (node_type*)pos.ptr->next );
	}

	iterator erase_after( iterator beforeFirst, iterator last )
	{
		EraseAfter( beforeFirst.ptr, last.ptr );
		return last;
	}


	void splice( iterator pos, this_type& l )
	{
		splice_after( previous(pos), l, l.before_begin(), l.before_end() );
	}

	void splice( iterator pos, this_type& l, iterator i )
	{
		splice_after( previous(pos), l, l.previous(i), i );
	}

	void splice( iterator pos, this_type& l, iterator first, iterator last )
	{
		splice_after( previous(pos), l, l.previous(first), l.previous(last) );
	}

	void splice_after( iterator pos, this_type& l ) { splice_after( pos, l, l.before_begin(), l.before_end() ); }
	void splice_after( iterator pos, this_type& l, iterator i ) { splice_after( pos, l, i, iterator((node_type*)i.ptr->next) ); }
	void splice_after( iterator pos, this_type& l, iterator beforeFirst, iterator beforeLast )
	{
		if( m_allocator == l.m_allocator )
		{
			size_t n = (size_t)fc::distance(beforeFirst, beforeLast);
			pos.ptr->splice_after( (node_type*)beforeFirst.ptr, (node_type*)beforeLast.ptr );
			l.m_size -= n;
			m_size += n;
		}
		else
		{
			l.EraseAfter( beforeFirst.ptr, (node_type*)beforeLast.ptr->next );
			InsertIterAfter( pos.ptr, const_iterator( (node_type*)beforeFirst.ptr->next ),
				const_iterator( (node_type*)beforeLast.ptr->next ) );
		}
	}

	void reverse()
	{
		_root.reverse();
	}

	void remove( const T& value )
	{
		node_type* first = (node_type*)_root.next;
		node_type* last = (node_type*)&_root;
		for( node_type* prev = last; first != last; prev = first, first = (node_type*)first->next )
			if( first->value == value )
				EraseAfter(prev), first = prev;
	}

	template <class Predicate>
	void remove_if( Predicate predicate )
	{
		node_type* first = (node_type*)_root.next;
		node_type* last = (node_type*)&_root;
		for( node_type* p, prev = last; first != last; first = p )
		{
			p = (node_type*)first->next;
			if( predicate(first->value) )
				EraseAfter(prev);
			else
				prev = first;
		}
	}

	template <class BinaryPredicate>
	void unique( BinaryPredicate predicate )
	{
		node_type* first = (node_type*)_root.next;
		node_type* last = (node_type*)&_root;
		if( first != last )
		{
			for( node_type* next = (node_type*)first->next; next != last; first = next, next = (node_type*)next->next )
				if( predicate(first->value, next->value) )
					EraseAfter( first ), next = first;
		}
	}

	void unique()
	{
		unique( equal_to<T>() );
	}

	template <class Compare> FC_NO_INLINE
	void merge( this_type& l, Compare compare )
	{
		iterator first1 = begin(), last1 = end();
		iterator first2 = l.begin(), last2 = l.end();
		while( (first1 != last1) && (first2 != last2) )
		{
			if( compare(*first2, *first1) )
			{
				node_type* p1 = (node_type*)first2.ptr;
				while( (++first2 != last2) && compare(*first2, *first1) )
					;
				first1.ptr->splice( p1, (node_type*)first2.ptr );
			}
			else
				++first1;
		}

		// append remaining to end of sequence.
		if( first2 != last2 )
			last1.ptr->splice( (node_type*)first2.ptr, (node_type*)last2.ptr );

		m_size += l.m_size;
		l.m_size = 0;
	}

	void merge( this_type& l )
	{
		merge( l, fc::less<T>() );
	}

	template <class Compare> FC_NO_INLINE
	void sort( Compare compare )
	{
		if( m_size < 2 )
			return;

		// todo: this can be optimized by splicing together bins.

		node_type newHead;
		node_type* pNewHead = &newHead;
		node_type* beforeLast2 = pNewHead;
		pNewHead->next = pNewHead;

		node_type* first = (node_type*)_root.next;
		node_type* last = (node_type*)&_root;

		for( node_type* next; first != last; first = next )
		{
			next = (node_type*)first->next;

			node_type* first2 = (node_type*)pNewHead->next;
			node_type* last2 = pNewHead;
			node_type* prev2 = last2;
			for( ; first2 != last2; prev2 = first2, first2 = (node_type*)first2->next )
			{
				if( compare(first->value, first2->value) )
				{
					first->next = first2;
					prev2->next = first;
					break;
				}
			}

			if( first2 == last2 )
			{
				beforeLast2 = first;
				first->next = last2;
				prev2->next = first;
			}
		}

		beforeLast2->next = (node_type*)&_root;
		_root.next = (node_type*)pNewHead->next;
	}

	void sort()
	{
		sort( less<T>() );
	}

	this_type& operator =( const this_type& l )
	{
		if( this != &l )
			assign( l.begin(), l.end() );

		return *this;
	}

	void swap( this_type& l )
	{
		if( m_allocator == l.m_allocator )
		{
			fc::swap( m_size, l.m_size );
			node_type::swap( _root, l._root );
		}
		else
		{
			this_type temp(*this);
			*this = l;
			l = temp;
		}
	}

protected:
	void EraseAfter( node_type* beforeFirst, node_type* last )
	{
		node_type* first = (node_type*)beforeFirst->next;
		for( node_type* next; first != last; first = next )
		{
			next = (node_type*)first->next;
			destroy_node(first);
			--m_size;
		}

		beforeFirst->next = last;
	}

	void EraseAfter( node_type* pos )
	{
		node_type* next = (node_type*)pos->next;
		next->unlink(pos);
		destroy_node(next);
		--m_size;
	}

	template <typename InputIterator>
	iterator InsertIterAfter( node_type* pos, InputIterator first, InputIterator last )
	{
		for( ; first != last; ++first, pos = (node_type*)pos->next )
			InsertAfter(pos, *first);

		return iterator(pos);
	}

	iterator InsertValuesAfter( node_type* pos, size_t n, const T& value )
	{
		for( ; n != 0; --n, pos = (node_type*)pos->next )
			InsertAfter(pos, value);

		return iterator(pos);
	}

	void InsertAfter( node_type* pos, const T& value )
	{
		node_type* p = create_node(value);
		p->link_after(pos);
		++m_size;
	}

};




// global slist operators

template <class T, class Allocator> inline
	void swap( const slist<T, Allocator>& a, const slist<T, Allocator>& b )
	{
		a.swap(b);
	}

template <class T, class A1, class A2> inline
	bool operator ==( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return( &a == &b || (a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin())) );
	}

template <class T, class A1, class A2> inline
	bool operator !=( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return !(a == b);
	}

template <class T, class A1, class A2> inline
	bool operator <( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return fc::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, class A1, class A2> inline
	bool operator >( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return b < a;
	}

template <class T, class A1, class A2> inline
	bool operator <=( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return !(b < a);
	}

template <class T, class A1, class A2> inline
	bool operator >=( const slist<T, A1>& a, const slist<T, A2>& b )
	{
		return !(a < b);
	}




FC_NAMESPACE_END

